#include "CliqueTree.h"

//#define DEBUG


CliqueTree::CliqueTree(Grafo g, unsigned int cantidadNodos, list<int>* r, list<int>* h, list<int> np, vector<int>& ord)
{
  cantNodos = cantidadNodos;
  rns = r;
  hijos = h;
  raices = new list<int>();
  chequeador = new bool[cantNodos];
  for(int i=0; i < cantNodos; i++){chequeador[i]=false;}
  nodosRaiz();
  grafo = g;
  orden = ord;
  setearNoPadres(np);
  crearOrdenNodos(orden);
}

CliqueTree::~CliqueTree()
{
  delete raices;
  delete[] noPadres;
  delete[] ordenNodos;
  delete[] chequeador;
}


void CliqueTree::crearOrdenNodos(vector<int> &orden)
{
  ordenNodos = new int[cantNodos];
  vector<int>::iterator it = orden.begin();
  for(unsigned int i = 0; i < orden.size(); i++, it++)
  {
    ordenNodos[*it] = i;
  }


}



void CliqueTree::setearNoPadres(list<int> np)
{
    noPadres = new int[cantNodos];

    list<int>::iterator itl = np.begin();
    for(int i=0; i < cantNodos, itl != np.end(); i++, itl++){
        noPadres[i] = *itl;
    }

 /* int i = 0;
  cout << ">>>>>> nopadres : ";
  for(list<int>::iterator itl = np.begin() ; itl != np.end(); itl++)
  {
    cout << "hijo: " << i << ", NP:  " << *itl << " ";
    i++;
  }
  cout << endl;*/

}

void CliqueTree::nodosRaiz()
{
  bool* tienePadre = new bool[cantNodos];
  for (unsigned int i = 0; i < cantNodos; i++)
  {
    tienePadre[i] = false;
  }

  for (unsigned int i = 0; i < cantNodos ; i++)
  {
    list<int> hs = hijos[i];
  	for (list<int>::iterator it = hs.begin(); it != hs.end(); it++)
  	{
  	  tienePadre[*it] = true;
  	}
  }

  setearNodosRaiz(tienePadre);
  delete[] tienePadre;
//  return resultado;
}

void CliqueTree::setearNodosRaiz(bool* tienePadre)
{
  //int resultado = cantNodos;
  unsigned int i = 0;
  while (i < cantNodos)
  {
  	if (not tienePadre[i])
  	{
  		//resultado = i;
  		raices->push_back(i);
  	}
  	i++;
  }

 /* cout << ">>>>>>raices : ";
  for(list<int>::iterator itl = raices->begin(); itl !=raices->end(); itl++)
  {
    cout << *itl << " ";
  }
  cout << endl;*/
 // assert(resultado != (int) cantNodos);
  return ; // resultado;
}

void CliqueTree::armarArbolDeCliques()
{
  while (not raices->empty()){

      //Idea: tener una lista de nodos y de cliques que al final se haga el delete.
      list<Clique*> repoCliques = list<Clique*>();
      list<Nodo*> repoNodos = list<Nodo*>();

      Arbol<Clique> arbol = Arbol<Clique>();
      list<Par> lista = list<Par>();
      Clique* cliqueInicial = new Clique();

      // meto el clique inicial en el repositorio.
      repoCliques.push_back(cliqueInicial);

      Nodo* nodoInicial = new Nodo(*cliqueInicial);
      // meto el nodo inicial en el repositorio.
      repoNodos.push_back(nodoInicial);
      arbol.establecerRaiz(*nodoInicial);

      lista.push_back(Par(raices->front(), nodoInicial));

      bool analizandoRaiz = true;

      list<Par>::iterator itl = lista.begin();
      while (not lista.empty())
      {
        Par p = lista.front();
        lista.pop_front(); // Esto llama al destructor de par. OJO!

        int x = p.first;
        #ifdef DEBUG
        cout << "Examinando " << x << endl;
        #endif

        Nodo& nodoCliquePadre = *(p.second);
        Clique& cliquePadre = nodoCliquePadre.elemento();

        #ifdef DEBUG
        cout << "Clique padre de " << x << ": " << cliquePadre << endl;
        #endif

        list<int> rnx = rns[x];
        list<int> rnpx = list<int>();

        #ifdef DEBUG
        cout << "RN(" << x << "): ";
        for (list<int>::iterator it = rnx.begin(); it != rnx.end(); it++)
        {
          cout << *it << " ";
        }
        cout << endl;
        #endif

        //cout << ";;;;;;;Comparando " << x << " con su parent " << noPadres[x] << endl;
        //cout << ";;;;;;;not esIgual(rnx, rnpx): " << not esIgual(rnx, rnpx) << endl;


        //si el nodo es una raiz, se inicializa el arbol con su clique vacia y forzando la entrada al else

        if ( !analizandoRaiz && (not esIgual(rnx, cliquePadre)) )
        {
          #ifdef DEBUG
          cout << "No est\'a incluido" << endl;
          #endif

          Clique* d = new Clique(); //Esto debe ser din'amico

          d -> agregarVertices(rnx);
          d -> agregarVertice(x);


          // agrego el clique nuevo al repositorio.
          repoCliques.push_back(d);


          Nodo* n = new Nodo(*d); //Esto debe ser din'amico
          // agrego el nodo al repositorio..
          repoNodos.push_back(n);
          nodoCliquePadre.agregarHijo(*n);
          apilarHijos(lista, x, *n);

          #ifdef DEBUG
          cout << "Nodo padre: " << nodoCliquePadre << endl;
          cout << "Nodo actual: " << *n << endl;
          #endif

          Arbol<Clique> temp = Arbol<Clique>();
          temp.establecerRaiz(nodoCliquePadre);

          #ifdef DEBUG
          cout << "Arbol desde el padre: " << temp << endl << endl;
          #endif
        }
        else
        {
          #ifdef DEBUG
          cout << "Est\'a incluido" << endl;
          #endif


          //marco que los siguientes nodos no son raices si vengo de analizar una
          if(analizandoRaiz){analizandoRaiz=false;}

           cliquePadre.agregarVertice(x);


          #ifdef DEBUG
          cout << "Clique con la inclusi\'on: " << cliquePadre << endl;
          #endif

          apilarHijos(lista, x, nodoCliquePadre);

          #ifdef DEBUG
          cout << "Nodo padre: " << nodoCliquePadre << endl;
          #endif

          Arbol<Clique> temp = Arbol<Clique>();
          temp.establecerRaiz(nodoCliquePadre);

          #ifdef DEBUG
          cout << "Arbol desde el padre: " << temp << endl << endl;
          #endif
        }
      }

      arbol.establecerRaiz(*(repoNodos.front()));
      cout << "---------------------------" << endl;
      cout << "Arbol final con nodo raiz "<< raices->front() <<" :" << endl;
      cout << arbol << endl;
      cout << "---------------------------" << endl;

      //habr'ia que hacer delete con las cosas din'amicas creadas.
      for (list<Nodo*>::iterator it = repoNodos.begin(); it != repoNodos.end();
        it++)
      {
       // if(true){cout << "Par "<< **it << endl;}
        delete *it;
      }
      for (list<Clique*>::iterator it = repoCliques.begin();
        it != repoCliques.end(); it++)
      {
        //if(true){cout << "Clique "<< **it << endl;}
        delete *it;
      }

      raices->pop_front();
  }
}




void CliqueTree::armarCoArbolDeCliques()
{
  while (not raices->empty()){


      //Idea: tener una lista de nodos y de cliques que al final se haga el delete.
      list<Clique*> repoCliques = list<Clique*>();
      list<Nodo*> repoNodos = list<Nodo*>();


      list<int> repoLeftmost = list<int>();


      Arbol<Clique> arbol = Arbol<Clique>();
      list<Par> lista = list<Par>();
      Clique* cliqueInicial = new Clique();



      // meto el clique inicial en el repositorio.
      repoCliques.push_back(cliqueInicial);



      Nodo* nodoInicial = new Nodo(*cliqueInicial);
      // meto el nodo inicial en el repositorio.
      repoNodos.push_back(nodoInicial);
      arbol.establecerRaiz(*nodoInicial);

      lista.push_back(Par(raices->front(), nodoInicial));

      bool analizandoRaiz = true;

      list<Par>::iterator itl = lista.begin();
      while (not lista.empty())
      {
        Par p = lista.front();
        lista.pop_front(); // Esto llama al destructor de par. OJO!

        int x = p.first;
        #ifdef DEBUG
        cout << "Examinando " << x << endl;
        #endif


        Nodo& nodoCliquePadre = *(p.second);
        Clique& cliquePadre = nodoCliquePadre.elemento();

        #ifdef DEBUG
        cout << "Clique padre de " << x << ": " << cliquePadre << endl;
        #endif

        list<int> rnx = rns[x];
        list<int> rnpx = list<int>();


        if(noPadres[x]!=cantNodos){rnpx = rns[noPadres[x]];}
        else{repoLeftmost.push_back(x);}


        #ifdef DEBUG
        cout << "RN(" << x << "): ";
        for (list<int>::iterator it = rnx.begin(); it != rnx.end(); it++)
        {
          cout << *it << " ";
        }
        cout << endl;
        #endif

        //cout << ";;;;;;;Comparando " << x << " con su parent " << noPadres[x] << endl;
        //cout << ";;;;;;;not esIgual(rnx, rnpx): " << not esIgual(rnx, rnpx) << endl;


        //si el nodo es una raiz, se inicializa el arbol con su clique vacia y forzando la entrada al else

        if ( !analizandoRaiz && (not esIgual(noPadres[x], rnx, rnpx)))
        {
          #ifdef DEBUG
          cout << "No est\'a incluido" << endl;
          #endif

          Clique* d = new Clique(); //Esto debe ser din'amico

          // agrego el clique nuevo al repositorio.
          repoCliques.push_back(d);

          repoLeftmost.push_back(x);

          Nodo* n = new Nodo(*d); //Esto debe ser din'amico
          // agrego el nodo al repositorio..
          repoNodos.push_back(n);
          nodoCliquePadre.agregarHijo(*n);
          apilarHijos(lista, x, *n);

          #ifdef DEBUG
          cout << "Nodo padre: " << nodoCliquePadre << endl;
          cout << "Nodo actual: " << *n << endl;
          #endif

          Arbol<Clique> temp = Arbol<Clique>();
          temp.establecerRaiz(nodoCliquePadre);

          #ifdef DEBUG
          cout << "Arbol desde el padre: " << temp << endl << endl;
          #endif
        }
        else
        {
          #ifdef DEBUG
          cout << "Est\'a incluido" << endl;
          #endif


          //marco que los siguientes nodos no son raices si vengo de analizar una
          if(analizandoRaiz){analizandoRaiz=false;}

          repoLeftmost.front()=x;

          #ifdef DEBUG
          cout << "Clique con la inclusi\'on: " << cliquePadre << endl;
          #endif

          apilarHijos(lista, x, nodoCliquePadre);

          #ifdef DEBUG
          cout << "Nodo padre: " << nodoCliquePadre << endl;
          #endif

          Arbol<Clique> temp = Arbol<Clique>();
          temp.establecerRaiz(nodoCliquePadre);

          #ifdef DEBUG
          cout << "Arbol desde el padre: " << temp << endl << endl;
          #endif
        }
      }


     #ifdef DEBUG

          cout << "repoLeftmost.size(): " <<  repoLeftmost.size() << endl;
          cout << "repoLeftmost: ";
          list<int>::iterator theIterator;
          for( theIterator = repoLeftmost.begin(); theIterator != repoLeftmost.end(); theIterator++ ) {
            cout << *theIterator << " " ;
          }

      cout << endl;
      #endif


           list<int>::iterator itLeft = repoLeftmost.begin();
           for (list<Clique*>::iterator it = repoCliques.begin();
                            it != repoCliques.end(); it++, itLeft++)
            {
              //cout << "leftmost " << *itLeft <<endl;
              pegarNoVecinos(*itLeft, *it);

            }



      arbol.establecerRaiz(*(repoNodos.front()));
      cout << "---------------------------" << endl;
      cout << "Arbol final con nodo raiz "<< raices->front() <<" :" << endl;
      cout << arbol << endl;
      cout << "---------------------------" << endl;

      //habr'ia que hacer delete con las cosas din'amicas creadas.
      for (list<Nodo*>::iterator it = repoNodos.begin(); it != repoNodos.end();
        it++)
      {
        //if(true){cout << "Par "<< **it << endl;}
        delete *it;
      }

      list<int>::iterator itLeft2 = repoLeftmost.begin();
      for (list<Clique*>::iterator it = repoCliques.begin();
        it != repoCliques.end(); it++, itLeft2++)
      {
        if(true){cout << "Clique: "<< **it << ", leftmost: " << *itLeft2 << endl;}
        delete *it;
      }

      raices->pop_front();
  }
}

void CliqueTree::apilarHijos(list<Par>& lista, int v, Nodo& n)
{
  list<int> hs = hijos[v];
  #ifdef DEBUG
  cout << "Hijos de " << v << ": ";
  #endif
  if (hs.size() > 0)
  {
    for (list<int>::iterator it = hs.begin(); it != hs.end() ; it++)
    {
      #ifdef DEBUG
      cout << *it << ' ';
      #endif

      lista.push_front(Par(*it, &n));
    }
    #ifdef DEBUG
    cout << endl;
    #endif
  }
  else
  {
    #ifdef DEBUG
    cout << "no tiene." << endl;
    #endif
  }

}

bool CliqueTree::esIgual(list<int>& rn, Clique& c)
{
  if (rn.size() == 0 and c.vertices.size() == 0)
  {
    return true;
  }


  if (rn.size() !=  c.vertices.size())
  {
    return false;
  }


  // Creo que si se empieza por rn, en lugar de c, da el orden.
  // rn se estar'ia chequeando una vez por cada nodo.
  list<int>::iterator it = rn.begin();
  while (it != rn.end())
  {
      chequeador[*it] = true;
      it++;
  }

  bool resultado = true;
  it = c.vertices.begin();
  while (resultado and it != c.vertices.end())
  {
  	resultado = chequeador[*it];
  	it++;
  }

  list<int>::iterator it2 = rn.begin();
  while (it2 != rn.end())
  {
      chequeador[*it2] =false;
      it2++;
  }


  return resultado;
}




bool CliqueTree::esIgual(int noPadre, list<int>& rn, list<int>& rnp)
{
  if (rn.size() == 0 and rnp.size() == 0)
  {
    return true;
  }



  list<int>::iterator it = rnp.begin();
  while (it != rnp.end())
  {
      chequeador[*it] = true;
      it++;
  }


  int tamRNDerechaNoPadre = 0;
  bool resultado = true;


  it = rn.begin();
  while (resultado and it != rn.end())
  {
    if( ordenNodos[*it] > ordenNodos[noPadre]){
  	resultado = chequeador[*it];
  	tamRNDerechaNoPadre++;
  	}
  	it++;
  }

  if(rnp.size()!=tamRNDerechaNoPadre){return false;}


  list<int>::iterator it2 = rnp.begin();
  while (it2 != rnp.end())
  {
      chequeador[*it2] =false;
      it2++;
  }


  return resultado;
}



void CliqueTree::pegarNoVecinos(int x, Clique* c){
    //EN REALIDAD PEGA LOS NO VECINOS A DERECHA, EL PAPER NO ES CLARO


  vector<int> temp = grafo.adyacencias(x);
 /* for(int i=0; i < temp.size(); i++){
      c->agregarVertice(temp[i]);
  }*/


  bool* chequeador = new bool[cantNodos];
  for (unsigned int i = 0; i < cantNodos; i++)
  {
  	chequeador[i] = false;
  }

  vector<int>::iterator it = temp.begin();
  while (it != temp.end())
  {
      //cout << "cheq = true para " << *it << endl;
      chequeador[*it] = true;
      it++;
  }

  int ordenX = ordenNodos[x];

  for(int i= ordenX ; i < cantNodos; i++){
      if(!chequeador[orden[i]]){
     // cout << "agregando vertice" << i << endl;
      c->agregarVertice(orden[i]);
      }
  }

  delete[] chequeador;
 }





